//for the time complexity, I estimate both are O(n)
//for the space complexity, the recursive one takes o(lgn) in the worst case(e.g. n = 2^m), whereas the iterative one takes O(1)
#include <cmath>
#include <iostream>
#include <queue>


int factor(int n, std::queue<int>& q) {
    if (n == 1)
        return 0;
    for (int i = 2; i <=sqrt(n); ++i) {
        int reminder = n % i;
        if( reminder == 0) { // n is a composite
            //return factor(i,q)+factor(n/i,q);
			return 1+factor(n/i,q); // i must be a prime
        }
    }
	q.push(n); //n is a prime
    return 1; 
}

int prime_factor_iterative(int n) {
	std::queue<int> factors;
	while( n > 1 ) {
		int i = 2;
		while(i <= sqrt(n) ) {
			int rem = n % i;
			if (rem == 0)
				break;
			++i;
		}
		if (i>sqrt(n)) { //n is prime
			factors.push(n);
			break;
		}
		else { // n is divided by i
			factors.push(i); //because n is always divided by a prime before a composite, i is guaranteed to be a prime
			n = n / i;
			i = 2;
		}
	}

	int num = factors.size();
	std::cout << "#prime factors: " << num << std::endl;
	while (!factors.empty()) {
		std::cout << factors.front() << " ";
		factors.pop();
	}
	std::cout << std::endl;
	return num;
}

void test_prime() { 
	int n = 90;
	std::queue<int> q;
	std::cout << "#prime factors: " << factor(n,q) << std::endl;
	while (!q.empty()) {
		std::cout << q.front() << " ";
		q.pop();
	}
	std::cout << std::endl;

	prime_factor_iterative(n);
}